package leetcode.editor.cn.q1_300.q;

/**
 * @author qidi
 * @date 2021-12-03 13:25:29
 */
class Q0045_JumpGameIi {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int jump(int[] nums) {
            if (nums.length == 1) return 0;
            // 一个长度为 n 的数组走到最后最多需要 n-1 步
            int step = 0;

            for (int i = 0; i < nums.length; ) {
                int max = 1;
                int index = i;

                if (index == nums.length - 1) return step;
                if (nums[index] + index >= nums.length - 1) {
                    return step + 1;
                }

                // 找到在 nums[i] 能覆盖的最大值
                for (int j = 1; j <= nums[i]; j++) {
                    if (i + j == nums.length) break;

                    if (j + nums[i + j] >= max) {
                        max = j + nums[i + j];
                        index = i + j;
                    }
                }
                step++;
                i = index;
            }

            return step;
        }

    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0045_JumpGameIi().new Solution();
        System.out.println(solution.jump(new int[]{2, 3, 1}));
        System.out.println(solution.jump(new int[]{1, 2}));
        System.out.println(solution.jump(new int[]{2, 3, 1, 1, 4}));
        System.out.println(solution.jump(new int[]{2, 3, 0, 1, 4}));
        System.out.println(solution.jump(new int[]{5, 6, 4, 4, 6, 9, 4, 4, 7, 4, 4, 8, 2, 6, 8, 1, 5, 9, 6, 5, 2, 7, 9, 7, 9, 6, 9, 4, 1, 6, 8, 8, 4, 4, 2, 0, 3, 8, 5}));
        System.out.println(solution.jump(new int[]{8, 2, 4, 4, 4, 9, 5, 2, 5, 8, 8, 0, 8, 6, 9, 1, 1, 6, 3, 5, 1, 2, 6, 6, 0, 4, 8, 6, 0, 3, 2, 8, 7, 6, 5, 1, 7, 0, 3, 4, 8, 3, 5, 9, 0, 4, 0, 1, 0, 5, 9, 2, 0, 7, 0, 2, 1, 0, 8, 2, 5, 1, 2, 3, 9, 7, 4, 7, 0, 0, 1, 8, 5, 6, 7, 5, 1, 9, 9, 3, 5, 0, 7, 5}));
        System.out.println(solution.jump(new int[]{5, 8, 1, 8, 9, 8, 7, 1, 7, 5, 8, 6, 5, 4, 7, 3, 9, 9, 0, 6, 6, 3, 4, 8, 0, 5, 8, 9, 5, 3, 7, 2, 1, 8, 2, 3, 8, 9, 4, 7, 6, 2, 5, 2, 8, 2, 7, 9, 3, 7, 6, 9, 2, 0, 8, 2, 7, 8, 4, 4, 1, 1, 6, 4, 1, 0, 7, 2, 0, 3, 9, 8, 7, 7, 0, 6, 9, 9, 7, 3, 6, 3, 4, 8, 6, 4, 3, 3, 2, 7, 8, 5, 8, 6, 0}));
    }
}